//给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。 
//
// 
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "google"
//输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 3： 
//
// 
//输入：s = "a"
//输出：[["a"]] 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
//
// 
//
// 
// 注意：本题与主站 131 题相同： https://leetcode-cn.com/problems/palindrome-partitioning/ 
//
// Related Topics 深度优先搜索 广度优先搜索 图 哈希表 👍 79 👎 0


package LeetCode.editor.cn;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-03-31 11:24:42
 * @description LCR 086.分割回文串
 
 */
 
public class M99OJA {
    public static void main(String[] args) {
    //测试代码
    M99OJA fun = new M99OJA();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //1.先预处理数组dp[i][j]表示i~j是否是回文，然后回溯处理所有分割方式
        //2.直接dfs+记忆化搜索
    //可以先用List处理，然后转为数组
    public String[][] partition1(String s) {
        List<List<String>> res=new ArrayList<>();
        int n=s.length();
        boolean [][] dp=new boolean[n][n];
        //长度是1的一定是回文
        Arrays.setAll(dp,i->{
            boolean[] row=new boolean[n];
            row[i]=true;
            return row;
        });
        char[] chars = s.toCharArray();
        //从长度为2开始枚举
        for (int len = 2; len <=n; len++) {
            for (int l = 0; l < n; l++) {
                //由 len=r-l+1, 得出右边界
                int r=len+l-1;
                if(r>=n) break;

                if(chars[l]!=chars[r]){
                    dp[l][r]=false;
                }else {
                    //包含 22 和212两种情况
                    if(r-l<3){
                        dp[l][r]=true;
                    }else {
                        dp[l][r]=dp[l+1][r-1];
                    }
                }
            }
        }
        dfs1(s,0,dp,new ArrayList<>(),res);
        return res.stream()
                .map(list -> list.toArray(String[]::new))
                .toArray(String[][]::new);
    }

    private void dfs1(String s, int i, boolean[][] dp, List<String> path, List<List<String>> res) {
        if(i==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int r = i; r < s.length(); r++) {
            if(dp[i][r]){
                path.add(s.substring(i,r+1));
                dfs1(s,r+1,dp,path,res);
                path.remove(path.size()-1);
            }
        }

    }
    int [] [] dp;
    List<List<String>> res=new ArrayList<>();
    List<String > path=new ArrayList<>();
    int n;
    //法2 dfs+记忆化搜索
    public String[][] partition(String s) {
        n=s.length();
        dp=new int[n][n];
        dfs(s,0);
        return res.stream().map(list->list.toArray(String[]::new)).toArray(String[][]::new);
    }

    private void dfs(String s, int i) {
        if (i==n){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < n; j++) {
            if(isPalindrome(s,i,j)==1){
                path.add(s.substring(i,j+1));
                dfs(s,j+1);
                path.remove(path.size()-1);
            }
        }
    }
    //0是初始值，-1代表不是，1代表是
    //可以递归的得出所有位置的回文情况
    //传入 0 1，则判断是否相等， 传入 0 2，则判断s[0]s[2]是否相等和dp[1][1]是否是1
    private int isPalindrome(String s, int i, int j) {
        if(dp[i][j]!=0) return dp[i][j];
        if(i>=j) dp[i][j]=1;
        else if(s.charAt(i)==s.charAt(j)) dp[i][j]=isPalindrome(s,i+1,j-1);
        else dp[i][j]=-1;
        return dp[i][j];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
